package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;

/**
 * 大佬提供的双指针/滑动窗口/子串问题的模板
 * TZPDO 不熟, 这个还得看
 * <p>
 * https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems
 * 虽然短, 可读性为0, LC76_4扩展为可读性好的
 * 这可太秀了.
 * 其实思想很像, 但是技巧和模板不错的
 * <p>
 * 76问题的similar question很多
 * LC438
 * LC3
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC76_4 implements TwoProblem {

    public String minWindow(String s, String t) {
        //小技巧, 字符串问题, 字符串有限, 可以不用map
        //小技巧, xx存的是各字母所需要的个数/所缺少的个数, 可以为负数的.
        int[] xx = new int[128];
        for (int i = 0; i < t.length(); i++) {
            xx[t.charAt(i)]++;
        }
        //counter和xx都是倒着用的, 正常我们是已满足0个, ++, 直到满足目标target
        //counter和xx是目前需要满足的个数, --,
        int counter = t.length(), begin = 0, end = 0, minSubLength = Integer.MAX_VALUE, head = 0;
        while (end < s.length()) {
            final char c1 = s.charAt(end);
            if (xx[c1] > 0) //是所缺字母, 则counter--
                counter--;
            xx[c1]--;//移动右指针
            end++; //移动右指针
            while (counter == 0) { //valid
                if (end - begin < minSubLength) { //判断并取min
                    minSubLength = end - begin;
                    head = begin;
                }
                final char c2 = s.charAt(begin);
                if (xx[c2] == 0)
                    counter++;//make it invalid
                xx[c2]++;//移动左指针
                begin++;//移动左指针
            }
        }
        return minSubLength == Integer.MAX_VALUE ? "" : s.substring(head, head + minSubLength);
    }

    public static void main(String[] args) {
        System.out.println(new LC76_4().minWindow("ADOBECODEBANC", "AABC"));
        System.out.println(new LC76_4().minWindow("AZZZZZAxBxCZZZZZCZ", "ABC"));
        System.out.println(new LC76_4().minWindow("a", "aa"));
        System.out.println(new LC76_4().minWindow("a", "ab"));
        System.out.println(new LC76_4().minWindow("cabwefgewcwaefgcf", "cae"));
    }
}
